package sort;

import com.sun.org.apache.xpath.internal.WhitespaceStrippingElementMatcher;
import jdk.nashorn.internal.ir.WhileNode;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Zhouchb
 * @Create 2021-10-2021/10/26 :17:25
 * @Description
 */
public class ShellSort {

    public static void main(String[] args) throws Exception {
      //  Integer[] i = {13,3, 9, 1, 8, 5, 4, 7};
        Integer[] i = {9,1, 2, 5, 7, 4, 8, 6,3,5};
/*        PrintStream printStream = new PrintStream("src\\info.txt");
        System.setOut(printStream);
        for (int k=100000;k>0;k--){
            System.out.println(k);
        }*/
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(ShellSort.class.getClassLoader().getResourceAsStream("info.txt")));
        String line = null;
        List list = new ArrayList<>();
        while ((line = bufferedReader.readLine())!=null){
           list.add(Integer.parseInt(line));
        }
        bufferedReader.close();
        Integer[] arr = new Integer[list.size()];
        list.toArray(arr);
        long start = System.currentTimeMillis();
        sort(arr);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }
    public static void sort(Comparable[] arr) {
       int h = 1;
        while (h<arr.length/2){
            h=h*2+1;
        }
        while (h>=1){
            for (int i=h;i< arr.length;i++){
                for (int j=i;j>=h;j-=h){
                  //  System.out.print(j+",");
                    if (compare(arr[j-h],arr[j])){
                        swap(arr,j-h,j);
                    }else {
                        break;
                    }
                }
              //  System.out.println();
            }
         //   System.out.println("**************");
            h=h/2;
        }
    }

    public static boolean compare(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    public static void swap(Comparable[] arr, int i, int j) {
        Comparable c;
        c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
}
